package everything.search.trees;

import java.util.Map;
import java.util.TreeMap;

import everything.WorldMap;
import everything.search.AgentState;
import everything.search.agents.IntelligentMaxiMaxAgent;
import everything.search.trees.nodes.GameTreeMaxiMaxNode;
import everything.search.trees.nodes.GameTreeNode;

public class GameTreeSearchMaxiMaxWithPruning extends GameTreePruningSearch {

	public GameTreeSearchMaxiMaxWithPruning(WorldMap map, int id, int idOp) {
		super(map, id, idOp);
	}
	
	@Override
	protected GameTreeNode searchWithParam(AgentState state, int ply) {
		GameTreeMaxiMaxNode node = new GameTreeMaxiMaxNode(state, null, 0, 0, null);
		GameTreeMaxiMaxNode n = searchMax(node, ply, Integer.MIN_VALUE, Integer.MIN_VALUE);
		node.setValue(n.getValue());
		node.setOpValue(n.getOpValue());
		return n;
	}
	
//	public GameTreeNode search(AgentState state, int ply){
//		GameTreeNode node = new GameTreeMaxiMaxNode(state, null, 0, 0, null);
//		log("STARTING SEARCH FOR " + _id + " ("+ply+") WITH " + state);
//		GameTreeNode searchNode = searchMax(node, ply, Integer.MIN_VALUE, Integer.MIN_VALUE);
//		node.setValue(searchNode.getValue());
//		GameTreeNode tmp = searchNode;
//		while (tmp.getParent()!=null){
//			System.out.println("BACKTRACK: " + tmp.getMove() + "  "+tmp.getValue()+", " + ((GameTreeMaxiMaxNode)tmp).getOpValue()+ " " + tmp.getState());
//			tmp = tmp.getParent();
//		}
//		System.out.println("BACKTRACK: " + tmp.getMove() + "  "+tmp.getValue()+", " + ((GameTreeMaxiMaxNode)tmp).getOpValue()+ " " + tmp.getState());
//		return searchNode;
//	}

	protected GameTreeMaxiMaxNode searchMax(GameTreeNode node, int ply, double alpha, double beta){
		AgentState state = node.getState();
		
		GameTreeNode storedState = checkState(state); 
		if (storedState!=null){
			return (GameTreeMaxiMaxNode)storedState;
		}
		
		Map<String, AgentState> expansions = new TreeMap<String, AgentState>();
		expansions.put("North", getNextState(state, "North", false));
		expansions.put("South", getNextState(state, "South", false));
		expansions.put("West", getNextState(state, "West", false));
		expansions.put("East", getNextState(state, "East", false));
		expansions.put("Fire", getNextState(state, "Fire", false));

		GameTreeMaxiMaxNode optimalValue = null;
		for (Map.Entry<String, AgentState> t: expansions.entrySet()){
			if (t.getValue().isTerminal() || ply == 0){
				double utility = IntelligentMaxiMaxAgent.utility(_id, t.getValue(),_map);
				double opUtility = IntelligentMaxiMaxAgent.utility(_idOp, t.getValue(),_map);
				if (optimalValue == null || optimalValue.getValue() < utility){
					node.setValue(utility);
					((GameTreeMaxiMaxNode)node).setOpValue(opUtility);
					optimalValue = new GameTreeMaxiMaxNode(t.getValue(), node, utility, opUtility, t.getKey());
				}
				alpha = Math.max(optimalValue.getValue(), alpha);
				log("Found terminal - " + _id +" - MAX (" +ply+") ["+utility+", " +opUtility+"]: " + t.getValue() + "  " + t.getKey());
			} else {
				GameTreeMaxiMaxNode subTreeRoot = new GameTreeMaxiMaxNode(t.getValue(), node, Integer.MIN_VALUE, Integer.MIN_VALUE, t.getKey());
				GameTreeMaxiMaxNode subTreeAns = searchMin(subTreeRoot, ply-1, alpha, beta);
				if (optimalValue == null || optimalValue.getValue() < subTreeAns.getValue()){
					subTreeRoot.setValue(subTreeAns.getValue());
					subTreeRoot.setOpValue(subTreeAns.getOpValue());
					optimalValue = subTreeAns;
					alpha = Math.max(optimalValue.getValue(), alpha);
					if (optimalValue.getOpValue() <= beta){
						log(beta + " beta sup");
						storeState(state, optimalValue);
						return optimalValue;
					}
				}
				log("Expanding - " + _id +" - MAX (" +ply+") ["+subTreeAns.getValue()+", " + subTreeAns.getOpValue()+"]: " + t.getValue() + "  " + t.getKey());
			}
		}
		storeState(state, optimalValue);
		return optimalValue;

	}
	protected GameTreeMaxiMaxNode searchMin(GameTreeNode node, int ply, double alpha, double beta){

		AgentState state = node.getState();
		
		GameTreeNode storedState = checkState(state); 
		if (storedState!=null){
			return (GameTreeMaxiMaxNode)storedState;
		}
		
		Map<String, AgentState> expansions = new TreeMap<String, AgentState>();
		expansions.put("North", getNextOpState(state, "North", false));
		expansions.put("South", getNextOpState(state, "South", false));
		expansions.put("West", getNextOpState(state, "West", false));
		expansions.put("East", getNextOpState(state, "East", false));
		expansions.put("Fire", getNextOpState(state, "Fire", false));

		GameTreeMaxiMaxNode optimalValue = null;
		for (Map.Entry<String, AgentState> t: expansions.entrySet()){
			if (t.getValue().isTerminal()){
				//TODO not needed for terminals (opponenet's move) since this is a whole search tree
				double utility = IntelligentMaxiMaxAgent.utility(_id, t.getValue(),_map);
				double opUtility = IntelligentMaxiMaxAgent.utility(_idOp, t.getValue(),_map);
				if (optimalValue == null || optimalValue.getOpValue() < opUtility){
					node.setValue(utility);
					((GameTreeMaxiMaxNode)node).setOpValue(opUtility);
					optimalValue = new GameTreeMaxiMaxNode(t.getValue(), node, utility, opUtility, t.getKey());
				}
				beta = Math.max(optimalValue.getOpValue(), beta);
				log("Found terminal - " + _id +" - MIN (" +ply+") ["+utility+", "+opUtility+"]: " + t.getValue() + "  " + t.getKey());
			} else {
				GameTreeMaxiMaxNode subTreeRoot = new GameTreeMaxiMaxNode(t.getValue(), node, Integer.MIN_VALUE, Integer.MIN_VALUE, t.getKey());
				GameTreeMaxiMaxNode subTreeAns = searchMax(subTreeRoot, ply-1, alpha, beta);
				if (optimalValue == null || optimalValue.getOpValue() < subTreeAns.getOpValue()){
					subTreeRoot.setValue(subTreeAns.getValue());
					subTreeRoot.setOpValue(subTreeAns.getOpValue());
					optimalValue = subTreeAns;
					beta = Math.max(optimalValue.getOpValue(), beta);
					if (optimalValue.getValue() <= alpha) {
						log(alpha + " alpha sup");
						storeState(state, optimalValue);
						return optimalValue;
					}
				}
				log("Expanding - " + _id +" - MIN (" +ply+") ["+subTreeAns.getValue()+", " +subTreeAns.getOpValue()+"]: " + t.getValue() + "  " + t.getKey());
			}
		}
		storeState(state, optimalValue);
		return optimalValue;
	}
}
